#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <queue>
using namespace std;
  struct ListNode {
 	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
  };
 
class Comp
{
public:
    bool operator()(ListNode* n1, ListNode* n2)
    {
        return n1->val > n2->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
        for (int i = 0;i < lists.size();++i)
        {
            if (lists[i])
                pq.push(lists[i]);
        }
        ListNode* ret = nullptr;
        ListNode* tail = ret;
        while (!pq.empty())
        {
            ListNode* top = pq.top();
            pq.pop();
            if (top->next)
            {
                pq.push(top->next);
            }
            if (tail == nullptr)
            {
                ret = top;
                tail = ret;
                tail->next = nullptr;
            }
            else
            {
                top->next = nullptr;
                tail->next = top;
                tail = tail->next;
            }
        }
        return ret;
    }
};